package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (B卷,200分)- 周末爬山（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 周末小明准备去爬山锻炼，0代表平地，山的高度使用1到9来表示，小明每次爬山或下山高度只能相差k及k以内，每次只能上下左右一个方向上移动一格，小明从左上角(0,0)位置出发
 * <p>
 * 输入描述
 * <p>
 * 第一行输入m n k(空格分隔)
 * <p>
 * 代表m*n的二维山地图，k为小明每次爬山或下山高度差的最大值，
 * 然后接下来输入山地图，一共m行n列，均以空格分隔。取值范围：
 * <p>
 * 0 < m ≤ 500
 * 0< n ≤ 500
 * 0 < k < 5
 * <p>
 * 输出描述
 * <p>
 * 请问小明能爬到的最高峰多高，到该最高峰的最短步数，输出以空格分隔。
 * <p>
 * 同高度的山峰输出较短步数。
 * <p>
 * 如果没有可以爬的山峰，则高度和步数都返回0。
 * <p>
 * 备注
 * 所有用例输入均为正确格式，且在取值范围内，考生不需要考虑不合法的输入格式。
 * <p>
 * 用例
 * <p>
 * 输入	5 4 1
 * <p>
 * 0 1 2 0
 * <p>
 * 1 0 0 0
 * <p>
 * 1 0 1 2
 * <p>
 * 1 3 1 0
 * <p>
 * 0 0 0 9
 * <p>
 * 输出	2 2
 * <p>
 * 说明	根据山地图可知，能爬到的最高峰在(0,2)位置，高度为2，最短路径为(0,0)-(0,1)-(0,2)，最短步数为2。
 * <p>
 * 输入	5 4 3
 * <p>
 * 0 0 0 0
 * <p>
 * 0 0 0 0
 * <p>
 * 0 9 0 0
 * <p>
 * 0 0 0 0
 * <p>
 * 0 0 0 9
 * <p>
 * 输出	0 0
 * <p>
 * 说明	根据山地图可知，每次爬山距离3，无法爬到山峰上，步数为0。
 */
public class BFSClimbingMountainsOnWeekends {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();
        k = sc.nextInt();

        matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }*/

        int m = 5;
        int n = 4;
        int k = 1;

        String input = "0 1 2 0\n1 0 0 0\n1 0 1 2\n1 3 1 0\n0 0 0 9";
        int[][] matrix = Arrays.stream(input.split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(matrix, k));
    }

    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    static int maxHeight;
    static int minStep;

    public static String getResult(int[][] matrix, int k) {
        // 到达matrix[0][0]高度的山峰，最短步数是0
        maxHeight = matrix[0][0];
        minStep = 0;

        // 广搜
        bfs(matrix, k);

        if (minStep == 0) {
            // 输出描述：如果没有可以爬的山峰，则高度和步数都返回0。
            return "0 0";
        } else {
            return maxHeight + " " + minStep;
        }
    }

    /**
     * 二维坐标
     *
     * @param matrix
     * @param k
     */
    public static void bfs(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 广搜队列
        LinkedList<int[]> queue = new LinkedList<>();
        // 访问记录
        boolean[][] visited = new boolean[m][n];

        // 首先是(0,0)位置进入队列，且被标记为访问过
        queue.add(new int[]{0, 0});
        visited[0][0] = true;

        // 此时消耗步数为0
        int step = 0;

        while (queue.size() > 0) {
            // 这里没有用queue.removeFirst来控制广搜，而是使用newQueue来控制广搜，因为这样更方便操作step
            LinkedList<int[]> newQueue = new LinkedList<>();

            boolean flag = false; // 广度层级遍历的步数计数

            while (queue.size() > 0) {

                // 遍历同一层的所有节点
                int[] lastPos = queue.poll();
                int x = lastPos[0];
                int y = lastPos[1];

                int lastHeight = matrix[x][y];

                // 四个方向位置
                for (int[] offset : offsets) {
                    int newX = x + offset[0];
                    int newY = y + offset[1];

                    // 新位置越界则无法继续广搜
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }

                    // 新位置已访问过，则无需重复广搜
                    if (visited[newX][newY]) {
                        continue;
                    }

                    int curHeight = matrix[newX][newY];

                    // 前后位置高度差在k以内, 则可以进入新位置
                    if (Math.abs(curHeight - lastHeight) <= k) {
                        // 标记新位置已访问
                        visited[newX][newY] = true;

                        if (!flag) { // 广度层级遍历的步数计数
                            flag = true;
                            step++;
                        }

                        // 如果此时到达新位置高度的步数step更小，则更新对应高度的最小步数
                        if (curHeight > maxHeight || (curHeight == maxHeight && step < minStep)) {
                            maxHeight = curHeight;
                            minStep = step;
                        }

                        // 新位置加入下一层广搜队列
                        newQueue.offer(new int[]{newX, newY});
                    }
                }
            }
            queue = newQueue;
        }
    }
}